# 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
#  实现词典类 WordDictionary ：
#  WordDictionary() 初始化词典对象
#  void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
#  bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
#
#  示例：
# 输入：
# ["WordDictionary","addWord","addWord","addWord","search","search","search","search"][[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
# 输出：
# [null,null,null,null,false,true,true,true]
#
# 解释：
# WordDictionary wordDictionary = new WordDictionary();
# wordDictionary.addWord("bad");
# wordDictionary.addWord("dad");
# wordDictionary.addWord("mad");
# wordDictionary.search("pad"); // return False
# wordDictionary.search("bad"); // return True
# wordDictionary.search(".ad"); // return True
# wordDictionary.search("b.."); // return True
import collections


# 实现方式二：hash表(key: 字符串长度 value 相同长度的字符串组成的set)
class WordDictionary2:
    def __init__(self):
        self.allWords = collections.defaultdict(set)

    def addWord(self, word: str) -> None:
        tmp = self.allWords[len(word)]
        if word not in tmp:
            tmp.add(word)

    def search(self, target: str) -> bool:
        wordLen = len(target)
        possibleWords = self.allWords[wordLen]

        def equals(possibleWord: str) -> bool:
            for i in range(wordLen):
                if target[i] == '.':
                    continue
                if possibleWord[i] != target[i]:
                    return False
            return True

        for s in possibleWords:
            if equals(s):
                return True
        return False


# 实现方式一： 字典树+回溯算法
class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False


class WordDictionary:

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        tmp = self.root
        for ch in word:
            index = ord(ch) - 97
            if not tmp.children[index]:
                tmp.children[index] = TrieNode()
            tmp = tmp.children[index]
        tmp.isEnd = True

    def search(self, word: str) -> bool:
        def dfs(root: TrieNode, word: str) -> bool:
            if not root:
                return False
            tmp = root
            for i, ch in enumerate(word):
                if ch == '.':  # 遇到'.'时遍历当前层所有非空节点并递归进行深度搜索之后的节点直到搜索到最下层或者搜索到目标字符串长度的层数
                    for j in range(26):
                        if tmp.children[j] and dfs(tmp.children[j], word[i + 1:]):
                            return True
                    return False

                # 搜索时普通字符还是按照经典的Trie进行搜索
                index = ord(ch) - 97
                if not tmp.children[index]:
                    return False
                tmp = tmp.children[index]
            return tmp.isEnd
        return dfs(self.root, word)


if __name__ == "__main__":
    wordDictionary = WordDictionary()
    # wordDictionary.addWord("bad")
    # wordDictionary.addWord("dad")
    # wordDictionary.addWord("mad")
    # print(wordDictionary.search("pad"))  # return False
    # print(wordDictionary.search("bad"))  # return True
    # print(wordDictionary.search(".ad"))  # return True
    # print(wordDictionary.search("b.."))  # return True
    # print(wordDictionary.search("b..."))  # return False

    wordDictionary.addWord("at")
    wordDictionary.addWord("and")
    wordDictionary.addWord("an")
    wordDictionary.addWord("add")
    print(wordDictionary.search("a"))  # return False
    print(wordDictionary.search(".at"))  # return False
    wordDictionary.addWord("bat")
    print(wordDictionary.search(".at"))  # return True
    print(wordDictionary.search("an."))  # return True
    print(wordDictionary.search("a.d."))  # return False
    print(wordDictionary.search("b."))  # return False
    print(wordDictionary.search("a.d"))  # return True
    print(wordDictionary.search("."))  # return False
